class Solution
{
public:
    int minimumPartition(string s, int k)
    {
        string ks = to_string(k);
        if (s.size() < ks.size())
        {
            return 1;
        }
        string_view sv(s);
        string_view kv(ks);

        int n = s.size();
        int kLen = ks.size();
        vector<int> dp(n, -1);

        for (int i = 0; i < kLen - 1; ++i)
        {
            dp[i] = 1;
        }
        for (int partLen = 1; partLen < kLen; ++partLen)
        {
            if (dp[kLen - 1 - partLen] != -1)
            {
                if (dp[kLen - 1] == -1)
                {
                    dp[kLen - 1] = dp[kLen - 1 - partLen] + 1;
                }

                else
                {
                    dp[kLen - 1] = min(dp[kLen - 1], dp[kLen - 1 - partLen] + 1);
                }
            }
        }
        if (sv.substr(0, kLen) <= kv)
        {
            dp[kLen - 1] = 1;
        }

        for (int i = kLen; i < n; ++i)
        {

            for (int partLen = 1; partLen < kLen; ++partLen)
            {
                if (dp[i - partLen] != -1)
                {
                    if (dp[i] == -1)
                    {
                        dp[i] = dp[i - partLen] + 1;
                    }
                    else
                    {
                        dp[i] = min(dp[i], dp[i - partLen] + 1);
                    }
                }
            }
            if (dp[i - kLen] != -1 && sv.substr(i - kLen + 1, kLen) <= kv)
            {
                if (dp[i] == -1)
                {
                    dp[i] = dp[i - kLen] + 1;
                }
                else
                {
                    dp[i] = min(dp[i], dp[i - kLen] + 1);
                }
            }
        }
        return dp[n - 1];
    }
};